home *** CD-ROM | disk | FTP | other *** search
/ Libris Britannia 4 / science library(b).zip / science library(b) / DDJMAG / DDJ8904.ZIP / MEMCMP.ASC < prev    next >
Text File  |  1989-03-27  |  41KB  |  1,110 lines
  1. _A MEMORY ALLOCATION COMPACTION SYSTEM_
  2. by Steve Peterson
  3.  
  4.  
  5. [LISTING ONE]
  6.  
  7.  
  8. /****   mem.h           data structures for memory manager
  9.         S. Peterson     programmer      12/88
  10. */
  11. typedef unsigned char   byte;
  12. typedef unsigned int    uint;
  13.  
  14. /*      This structure is the header of a memory block.  It lies before
  15.         the actual memory block. */
  16. struct memBlkHdr {
  17.                 char                    checkByte; /* Header validation */
  18.                 byte                    flags;  /* Flags (see below) */
  19.                 byte                    segment;/* Segment of this block */
  20.                 struct memBlkHdr        *prev; /* Pointer-previous block */
  21.                 uint                    size; /* size of block */
  22.                 int                     pointerNum; /* Block master pointer */
  23.                 void                    (*func)(void *, byte, uint, void *);
  24.         } ;
  25.  
  26. typedef struct memBlkHdr MEMBLK;
  27.  
  28. /*      These are the definitions of each of the flags in the flags byte
  29.         of memBlkHdr. */
  30.  
  31. #define BLK_INUSE       0x01    /* Block is allocated */
  32. #define BLK_DELETABLE   0x02    /* Block can be deleted */
  33. #define BLK_LOCKED      0x04    /* Block is locked */
  34. #define BLK_FUNCDELETE  0x08    /* Call block function on delete */
  35. #define BLK_FUNCMOVE    0x10    /* Call block function on move */
  36. #define BLK_DELETED     0x20    /* Block has been deleted */
  37. #define BLK_LAST        0x40    /* Last block in segment */
  38.  
  39. /*      freePtr is stored at the beginning of the user part of a
  40.         free block.  It contains the links to next and previous free blocks
  41.         in the segment.  prev is NULL if this is the first free block, and
  42.         next is NULL if this is the last block */
  43.  
  44. struct  freePtr {
  45.                 MEMBLK  *prev;  /* Pointer to previous free block */
  46.                 MEMBLK  *next;  /* Pointer to next free block */
  47.         } ;
  48.  
  49. typedef struct freePtr FREEBLK;
  50.  
  51. /*      Macro to return address of data area give block header address */
  52.  
  53. #define DATALOC(xx)     ((byte *) (xx) + sizeof(MEMBLK))
  54.  
  55. /*      Macro to return address of header given data area address */
  56.  
  57. #define HEADERLOC(xx)   ((byte *) (xx) - sizeof(MEMBLK))
  58.  
  59. /*      This is an entry in the master block table. */
  60.  
  61. struct  masterSegmentEntry {
  62.                 void                *block;  /* Address, associated block */
  63.                 uint                size;    /* Size of block */
  64.                 uint                freeSpace; /* Amount of free space */
  65.                 struct memBlkHdr    *free;     /* First free block */
  66.                 struct memBlkHdr    *last;     /* Last reference free block */
  67.         } ;
  68.  
  69. #define DEFSEGSIZE              4096            /* Default segment size */
  70. #define CB                      'S'
  71.  
  72. /*      MINREMAINDER is the smallest free block that can remain after
  73.         allocation.  Making this larger reduces fragmentation but wastes
  74.         more space. */
  75.  
  76. #define MINREMAINDER            20
  77.  
  78. /*      MINBLOCKDATA is the smallest block data area that can be created. This
  79.         must be at least sizeof(FREEBLK) bytes so there is space for the
  80.         next and prev pointers stored in a free block. */
  81.  
  82. #define MINBLOCKDATA    (sizeof(FREEBLK))
  83.  
  84. /*      Function prototypes */
  85.  
  86. #ifndef NOPROTO
  87.  
  88. int     MemInit(long int, int);
  89. int     MemLocked(void **);
  90. void    MemLock(void **);
  91. void    MemUnlock(void **);
  92. void    MemDeletable(void **);
  93. void    MemUndeletable(void **);
  94. int     MemDeleted(void **);
  95. void    **MemAlloc(uint);
  96. void    **MemAllocFunc(uint,void (*)(void *,byte, uint, void *), uint);
  97. void    MemFree(void **);
  98. uint    MemGetLargest(void);
  99. uint    MemGetCurrentLargest(void);
  100. void    MemCompact(void);
  101.  
  102. #endif
  103.  
  104.  
  105. [LISTING TWO]
  106.  
  107. /*****  mem.c           Compactible memory manager
  108.         S. Peterson     programmer      12/88, 1/89
  109.         This module provides a memory management system with the following
  110.         features:
  111.         .       Relocatable memory blocks
  112.         .       Able to collapse fragemented free space
  113.         .       Disposable blocks
  114.         .       Lockable blocks
  115. */
  116.  
  117. #include        <stdio.h>
  118. #include        <stddef.h>
  119. #include        <malloc.h>
  120. #include        <string.h>
  121. #include        <process.h>
  122. #include        <stdlib.h>
  123. #include        <conio.h>
  124. #include        "mem.h"
  125.  
  126. /*      Static module data */
  127.  
  128. struct masterSegmentEntry *mst = NULL;          /* Master segment table */
  129.  
  130. byte    numSegs         = -1;   /* Number of whole & partial segments */
  131. byte    lastSeg         = -1;   /* Index of last segment used */
  132.  
  133. void    **mpt           = NULL; /* Master pointer table */
  134. int     numMP           = -1;   /* Number of master pointers allocated */
  135. int     mpFree          = -1;   /* Number of master pointers free */
  136. int     lastMP          = -1;   /* Last master pointer used */
  137.  
  138. /*      Local function declarations */
  139.  
  140. #ifndef NOPROTO
  141.  
  142. static int      FindFreeBlock(int, uint, void **);
  143. static int      AllocBlock(uint, void **, byte);
  144. static int      GetFreeMP(void);
  145. static void     ReleaseMP(int);
  146. static void     CompactSeg(byte, uint, int);
  147.  
  148. #endif
  149.  
  150. /**     MemInit -- initalize memory manager
  151.         Entry   lSize           size of requested memory in bytes
  152.                 nHandles        number of block handles to allocate
  153.         Exit    none
  154.         Returns TRUE            worked
  155.                 FALSE           failed
  156. **/
  157. int
  158. MemInit(lSize, nHandles)
  159. long int        lSize;
  160. int             nHandles;
  161. {
  162.         byte    numWhole;       /* Number of whole segments to create */
  163.         uint    numBytes;       /* Size of partial segment */
  164.         uint    createSize;     /* Size to create */
  165.         MEMBLK  *mbh;           /* Work block header */
  166.         int     i;              /* Work */
  167.         FREEBLK *f;             /* Free links */
  168.  
  169.         /* Allocate handle list */
  170.  
  171.         if ((mpt = (void **) malloc(sizeof(void *)*nHandles)) == NULL)
  172.                 return  FALSE;
  173.  
  174.         numMP = nHandles;
  175.         for (i = 0; i < numMP; mpt[i] = NULL, i++) ;
  176.         mpFree = numMP;
  177.         lastMP = 0;
  178.  
  179.         /* Determine size of segments to create */
  180.  
  181.         numWhole = (byte) (lSize / (long) DEFSEGSIZE);
  182.         numBytes = (uint) (lSize % (long) DEFSEGSIZE);
  183.         numSegs = numWhole + 1;
  184.         lastSeg = 0;
  185.  
  186.         if ((mst = (struct masterSegmentEntry *) malloc(sizeof
  187.                       (struct masterSegmentEntry)*(numSegs))) == NULL)
  188.                 return  FALSE;
  189.  
  190.         /* Allocate segments */
  191.  
  192.         for(i = 0; i < numSegs; i++) {
  193.                 if (i == numSegs - 2) {         /* Second to last */
  194.                         if (numBytes < DEFSEGSIZE / 4) {   /* Last is small */
  195.                                 numBytes += DEFSEGSIZE / 4;
  196.                                 createSize = DEFSEGSIZE - (DEFSEGSIZE / 4);
  197.                         } else {
  198.                                 createSize = DEFSEGSIZE;
  199.                         }
  200.                 } else if (i == numSegs - 1) {  /* Last */
  201.                         createSize = numBytes;
  202.                 } else {                        /* Whole segment */
  203.                         createSize = DEFSEGSIZE;
  204.                 }
  205.            if (createSize < sizeof(MEMBLK) + 10)
  206.                         return  FALSE;
  207.                 if ((mst[i].block = (void *) malloc(createSize)) == NULL)
  208.                         return  FALSE;
  209.                 mst[i].size = createSize;
  210.                 mst[i].freeSpace = createSize;
  211.  
  212.                 /* Allocate one block in segment */
  213.  
  214.                 mbh             = (MEMBLK *) mst[i].block;
  215.                 mst[i].free     = mbh;
  216.                 mst[i].last     = mbh;
  217.  
  218.                 mbh->checkByte  = CB;
  219.                 mbh->prev       = NULL;
  220.                 mbh->flags      = BLK_LAST;
  221.                 mbh->size       = mst[i].size;
  222.                 mbh->segment    = (byte) i;
  223.  
  224.                 /* Clear next and prev pointer area */
  225.  
  226.                 f = (FREEBLK *) DATALOC(mbh);
  227.                 f->prev = NULL;
  228.                 f->next = NULL;
  229.         }
  230.         return  TRUE;
  231. }
  232.  
  233. /**     MemLocked       -- test whether a block is locked
  234.         Entry   block           address of a block
  235.         Exit    none
  236.         Returns TRUE            block is locked
  237.                 FALSE           not locked
  238. **/
  239. int
  240. MemLocked(block)
  241. void    **block;
  242. {
  243.         return  !(((MEMBLK *) HEADERLOC(*block))->flags & BLK_LOCKED);
  244. }
  245.  
  246. /**     MemLock         -- locks a block into a particular location in memory
  247.         Entry   block           address of block to lock
  248.         Exit    none
  249.         Returns void
  250. **/
  251. void
  252. MemLock(block)
  253. void    **block;
  254. {
  255.         ((MEMBLK *) HEADERLOC(*block))->flags |= BLK_LOCKED;
  256. }
  257.  
  258. /**     MemUnlock               -- unlocks a block
  259.         Entry   block           address of block to unlock
  260.         Exit    none
  261.         Returns void
  262. **/
  263. void
  264. MemUnlock(block)
  265. void    **block;
  266. {
  267.         ((MEMBLK *) HEADERLOC(*block))->flags &= ~BLK_LOCKED;
  268. }
  269.  
  270. /**     MemDeletable            -- make a block deletable
  271.         Entry   block           address of block to mark as deletable
  272.         Exit    none
  273.         Returns void
  274. **/
  275. void
  276. MemDeletable(block)
  277. void    **block;
  278. {
  279.         ((MEMBLK *) HEADERLOC(*block))->flags |= BLK_DELETABLE;
  280. }
  281.  
  282. /**     MemUndeletable          -- mark a block as undeletable
  283.         Entry   block           address of block to mark
  284.         Exit    none
  285.         Returns void
  286. **/
  287. void
  288. MemUndeletable(block)
  289. void    **block;
  290. {
  291.         ((MEMBLK *) HEADERLOC(*block))->flags &= ~BLK_LOCKED;
  292. }
  293.  
  294. /**     MemIsDeleted    -- test whether a block has been deleted
  295.         Entry   block           address of a block
  296.         Exit    none
  297.         Returns TRUE            block is available
  298.                 FALSE           has been deleted
  299. **/
  300. int
  301. MemDeleted(block)
  302. void    **block;
  303. {
  304.         return  (((MEMBLK *) HEADERLOC(*block))->flags & BLK_DELETED) != 0;
  305. }
  306.  
  307.  
  308. /**     MemAlloc        -- allocate memory block
  309.         Entry   size            size of block to allocate
  310.         Exit    none
  311.         Returns pointer to created block, or NULL if not enough room to create
  312.         Notes   The function operates by first examining the current segment
  313.                 for a first fit to the requested size.  It then proceeds to
  314.                 the remaining blocks looking for a free block of adequate
  315.                 size.
  316.                 If no block exists that is large enough, it examines the
  317.                 segment list looking for a segment that can be compacted
  318.                 to produce enough room.  The segment with the fewest
  319.                 allocated blocks is favored for compaction.
  320.                 Possible enhancement:  if no segment has enough room, shuffle
  321.                 blocks between segments.
  322.                 If there is not enough room in any segment, the function
  323.                 fails.
  324. **/
  325. void **
  326. MemAlloc(size)
  327. uint    size;
  328. {
  329.         byte            curSeg;         /* Current segment */
  330.         byte            segIndex;       /* Index of segment in list */
  331.         long            ltotalFree      = 0l;  /* Total free space */
  332.         byte            maxFreeSeg      = 255; /* Segment, most free space */
  333.         uint            maxFreeSize     = 0;   /* Segment space, most space */
  334.         MEMBLK          *b;                    /* Block address to allocate */
  335.         int             created         = FALSE;        /* Block created */
  336.         int             mp;                             /* Master pointer */
  337.  
  338.         if ((mp = GetFreeMP()) < 0)
  339.                 return  NULL;
  340.  
  341.         if (size > DEFSEGSIZE - sizeof(MEMBLK))
  342.                 return  NULL;
  343.  
  344.         if (size < MINBLOCKDATA)        /* Smallest allocatable block */
  345.                 size = MINBLOCKDATA;
  346.         size += sizeof(MEMBLK);         /* Add header to block */
  347.  
  348.         /* First pass -- try to allocate from current block structure */
  349.  
  350.         for (segIndex = 0; (segIndex < numSegs) && (!created); segIndex++) {
  351.  
  352.                 curSeg = (lastSeg + segIndex) % numSegs;
  353.  
  354.                 /* Get stats */
  355.  
  356.                 ltotalFree += (long) mst[curSeg].freeSpace;
  357.  
  358.                 /* Is there enough space in the current segment to allocate? */
  359.  
  360.                 if (mst[curSeg].freeSpace >= size) {
  361.  
  362.                         if (maxFreeSize < mst[curSeg].freeSpace) {
  363.                                 maxFreeSize     = mst[curSeg].freeSpace;
  364.                                 maxFreeSeg      = curSeg;
  365.                         }
  366.  
  367.                         /* Search free list for first fit */
  368.  
  369.                         if (FindFreeBlock(curSeg, size, &b)) {
  370.  
  371.                                 /* Allocate */
  372.  
  373.                                 if (!(created = AllocBlock(size, &b, curSeg)))
  374.                                         return  FALSE;
  375.                         }
  376.                 }
  377.         }
  378.  
  379.         /* Which segment could be compacted to create a block large enough?
  380.            We kept track of the segment with the most free space.  This should
  381.            compact easily. */
  382.  
  383.         if (!created && (maxFreeSeg != 255)) {
  384.                 /* Compact to produce needed free space */
  385.  
  386.                 curSeg = maxFreeSeg;
  387.                 CompactSeg(curSeg, size, FALSE);
  388.  
  389.                 if (!FindFreeBlock(curSeg, size, &b)) {
  390.                         CompactSeg(curSeg, size, TRUE);
  391.  
  392.                         if (!FindFreeBlock(curSeg, size, &b))
  393.                                 return  NULL;
  394.                 }
  395.  
  396.                 if (!(created = AllocBlock(size, &b, curSeg)))
  397.                         return  FALSE;
  398.         }
  399.  
  400.         if (created) {
  401.                 mst[curSeg].freeSpace   -= b->size;
  402.                 mpt[mp]                 = DATALOC(b);
  403.                 b->pointerNum           = mp;
  404.                 b->func                 = NULL;
  405.                 lastSeg                 = curSeg;
  406.                 return  (void *) &(mpt[mp]);
  407.         } else {
  408.                 ReleaseMP(mp);
  409.                 return  NULL;
  410.         }
  411. }
  412.  
  413. /**     MemAllocFunc    -- allocate a memory block with an associated function
  414.         Entry   size    size of block to allocate
  415.                 func    function to call
  416.                 flags   following constants:
  417.                         BLK_FUNCDELETE  call function when block deleted
  418.                         BLK_FUNMOVE     call function when block moved
  419.         Exit    none
  420.         Returns pointer to allocated block, or NULL if no space available
  421.         Notes   Calls memAlloc to allocate memory
  422. **/
  423. void **
  424. MemAllocFunc(size, func, flags)
  425. uint    size;
  426. void    (*func)(void *, byte, uint, void *);
  427. uint    flags;
  428. {
  429.         void    **aBlock;               /* Allocated block */
  430.         MEMBLK  *b;                     /* Dereferenced block header */
  431.  
  432.         if ((aBlock = MemAlloc(size)) != NULL) {
  433.                 b = (MEMBLK *) HEADERLOC(*aBlock);
  434.                 b->flags |= flags & (BLK_FUNCMOVE | BLK_FUNCDELETE);
  435.                 b->func = func;
  436.                 return  aBlock;
  437.         } else {
  438.                 return  NULL;
  439.         }
  440. }
  441.  
  442. /**     FindFreeBlock   -- locate a free block in a segment
  443.         Entry   seg             segment to search
  444.                 size            bytes required for block including header
  445.         Exit    b               address of block header (if found)
  446.         Returns TRUE            block found
  447.                 FALSE           no space
  448.         Notes   Finds a free block in the current segment.  Starts
  449.                 with the last-referenced free block in the segment.  This
  450.                 spreads the allocations through the segment and combats
  451.                 fragmentation.
  452.                 The caller can save some time by first checking to see if
  453.                 the segment has enough free space to allocate the block.
  454.                 This algorithm uses the first-fit method, which is fast but
  455.                 promotes fragmentation.
  456. **/
  457. static int
  458. FindFreeBlock(seg, size, b)
  459. int     seg;
  460. uint    size;
  461. void    **b;
  462. {
  463.         MEMBLK  *m;                             /* Current memory block */
  464.  
  465.         m = mst[seg].last;
  466.  
  467.         if (m != NULL) {
  468.                 while (m->size < size) {
  469.                         if ((m = ((FREEBLK *) DATALOC(m))->next) == NULL) {
  470.                                 /* End of free list */
  471.                                 m = mst[seg].free;
  472.                         }
  473.  
  474.                         if (m == mst[seg].last)
  475.                                 break;
  476.                 }
  477.  
  478.                 if (m->size < size) {           /* No block large enough */
  479.                         *b = NULL;
  480.                         return  FALSE;
  481.                 } else {                        /* Block found */
  482.                         *b = m;
  483.                         return  TRUE;
  484.                 }
  485.         } else {                                /* No block */
  486.                 *b = NULL;
  487.                 return  FALSE;
  488.         }
  489. }
  490.  
  491. /**     AllocBlock      -- allocate a block
  492.         Entry   size            size of block (including header) to allocate
  493.                 b               address of block where it will be allocated
  494.         Exit    b               Address of allocated block header (this is
  495.                                 different that the b input parameter)
  496.         Returns TRUE            allocated
  497.                 FALSE           memory structure corrupt
  498.         Notes   This function takes a block and splits it in two.  If the
  499.                 remaining free block is small, the entire block is allocated
  500.                 and no free portion is created.  This can waste some memory,
  501.                 but avoids extreme fragmentation.
  502. **/
  503.  
  504. static int
  505. AllocBlock(size, b, segment)
  506. uint    size;
  507. void    **b;
  508. byte    segment;
  509. {
  510.         MEMBLK  *freeBlock;     /* Free block */
  511.         MEMBLK  *nextBlock;     /* Next block */
  512.         MEMBLK  *aBlock;        /* Allocated block */
  513.         FREEBLK *curFree;       /* Free pointers in block we are allocating */
  514.         FREEBLK *t;             /* Pointer to free block we are adjusting */
  515.  
  516.         freeBlock = (MEMBLK *) *b;
  517.  
  518.         if ((freeBlock->size - MINREMAINDER < size)) {
  519.  
  520.                 /* Whole block will be allocated */
  521.  
  522.                 aBlock                  = freeBlock;
  523.                 size                    = aBlock->size;
  524.                 aBlock->flags           |= BLK_INUSE;
  525.  
  526.                 curFree = (FREEBLK *) DATALOC(aBlock);
  527.  
  528.                 if (mst[segment].free == aBlock) {
  529.                         /* Implicit:  aBlock is first in list */
  530.                         mst[segment].free = curFree->next;
  531.                 }
  532.  
  533.                 if (curFree->next != NULL) {
  534.                         t = (FREEBLK *) DATALOC(curFree->next);
  535.                         t->prev = curFree->prev;
  536.                         mst[segment].last = curFree->next;
  537.                 } else if (curFree->prev != NULL) {
  538.                         t = (FREEBLK *) DATALOC(curFree->prev);
  539.                         t->next = curFree->next;
  540.                         mst[segment].last = curFree->prev;
  541.                 } else {                        /* No free block */
  542.                         mst[segment].last = NULL;
  543.                         mst[segment].free = NULL;
  544.                 }
  545.  
  546.         } else {        /* Block will be split */
  547.  
  548.                 aBlock = (MEMBLK *) ((byte *) freeBlock +
  549.                                               (freeBlock->size - size));
  550.                 aBlock->checkByte       = CB;
  551.                 aBlock->prev            = freeBlock;
  552.                 aBlock->flags           = BLK_INUSE;
  553.                 aBlock->size            = size;
  554.                 aBlock->segment         = segment;
  555.  
  556.                 freeBlock->size -= size;
  557.  
  558.                 /* Is block last in segment? */
  559.  
  560.                 if ((freeBlock->flags & BLK_LAST) != 0) {
  561.                         freeBlock->flags        &= ~BLK_LAST;
  562.                         aBlock->flags           |= BLK_LAST;
  563.                 } else {
  564.                     nextBlock = (MEMBLK *) ((byte *) aBlock + (aBlock->size));
  565.                     nextBlock->prev = aBlock;
  566.                 }
  567.         }
  568.  
  569.         *b = aBlock;
  570.         return  TRUE;
  571. }
  572.  
  573. /**     GetFreeMP       -- return next free master pointer
  574.         Entry   none
  575.         Exit    none
  576.         Returns index of next free master pointer
  577. **/
  578. static int
  579. GetFreeMP()
  580. {
  581.         int     i;
  582.  
  583.         if (mpFree == 0)
  584.                 return  -1;
  585.  
  586.         for (i = 0; i < numMP; i++, lastMP++) {
  587.                 if (lastMP >= numMP)
  588.                         lastMP = 0;
  589.                 if (mpt[lastMP] == 0) {
  590.                         mpFree--;
  591.                         return  lastMP;
  592.                 }
  593.         }
  594.  
  595.         return  -1;
  596. }
  597.  
  598. /**     ReleaseMP       -- release a master pointer to free pool
  599.         Entry   mp      master pointer to release
  600.         Exit    none
  601.         Returns void
  602. **/
  603. static void
  604. ReleaseMP(mp)
  605. int     mp;
  606. {
  607.         mpFree++;
  608.         mpt[mp] = NULL;
  609. }
  610.  
  611. /**     MemFree         -- free a block of memory
  612.         Entry   blockPtr        pointer to mpt entry for block
  613.         Exit    none
  614.         Returns none
  615. **/
  616. void
  617. MemFree(blockPtr)
  618. void    **blockPtr;
  619. {
  620.         MEMBLK  *cur;           /* Actual block */
  621.         FREEBLK *curFree;       /* Free block in current block */
  622.         MEMBLK  *workMem;       /* Work block in memory */
  623.         FREEBLK *workFree;      /* Work block in next block */
  624.         int     combined = FALSE; /* Has been combined */
  625.  
  626.         cur             = (MEMBLK *) HEADERLOC(*blockPtr);
  627.  
  628.         if (cur->checkByte != CB)
  629.                 return;
  630.  
  631.         ReleaseMP(cur->pointerNum);             /* blockPtr no longer valid */
  632.  
  633.         curFree         = (FREEBLK *) DATALOC(cur);
  634.  
  635.         /* Mark block as unallocated */
  636.  
  637.         cur->flags                      &= ~BLK_INUSE;
  638.         mst[cur->segment].freeSpace     += cur->size;
  639.  
  640.         /* Combine with subsequent block? */
  641.  
  642.         if ((cur->flags & BLK_LAST) == 0) {
  643.                 workMem = (MEMBLK *) ((byte *) cur + cur->size);
  644.  
  645.                 if ((workMem->flags & BLK_INUSE) == 0) {   /* unallocated */
  646.                         combined = TRUE;
  647.  
  648.                         if ((workMem->flags & BLK_LAST) != 0)
  649.                                 cur->flags |= BLK_LAST;
  650.  
  651.                         workFree = (FREEBLK *) DATALOC(workMem);
  652.                         curFree->next = workFree->next;
  653.                         curFree->prev = workFree->prev;
  654.                         cur->size += workMem->size;
  655.  
  656.                         /* New top of free list? */
  657.  
  658.                         if (workMem == mst[cur->segment].free)
  659.                                 mst[cur->segment].free = cur;
  660.  
  661.                         if (workMem == mst[cur->segment].last)
  662.                                 mst[cur->segment].last = cur;
  663.  
  664.                 /* Adjust pointers in free chain. Point to new block */
  665.  
  666.                         if (curFree->next != NULL) {
  667.                                 workFree = (FREEBLK *) DATALOC(curFree->next);
  668.                                 workFree->prev = cur;
  669.                         }
  670.  
  671.                         if (curFree->prev != NULL) {
  672.                                 workFree = (FREEBLK *) DATALOC(curFree->prev);
  673.                                 workFree->next = cur;
  674.                         }
  675.  
  676.                         /* Adjust previous block chain */
  677.  
  678.                         if ((cur->flags & BLK_LAST) == 0) {
  679.                                 workMem = (MEMBLK *) ((byte *) workMem +
  680.                                                                workMem->size);
  681.                                 workMem->prev = cur;
  682.                         }
  683.                 }
  684.         }
  685.  
  686.         /* Combine with previous block? */
  687.  
  688.         if (cur->prev != NULL) {
  689.                 workMem = cur->prev;
  690.  
  691.                 if ((workMem->flags & BLK_INUSE) == 0) { /* unallocated */
  692.                         workMem->size += cur->size;
  693.  
  694.                         if ((cur->flags & BLK_LAST) != 0)
  695.                                 workMem->flags |= BLK_LAST;
  696.                         cur->checkByte = '\0';
  697.  
  698.                         if (combined) {
  699.  
  700.                                 /* Eliminate free block from links */
  701.  
  702.                                 workFree = (FREEBLK *) DATALOC(workMem);
  703.                                 workFree->next = curFree->next;
  704.  
  705.                                 if (workFree->next != NULL) {
  706.                                         workFree = (FREEBLK *)
  707.                                                       DATALOC(workFree->next);
  708.                                         workFree->prev = workMem;
  709.                                 }
  710.  
  711.                         } else {
  712.  
  713.                                 /* Free block already linked */
  714.  
  715.                                 combined = TRUE;
  716.                         }
  717.  
  718.                         /* Connect block chain */
  719.  
  720.                         if ((cur->flags & BLK_LAST) == 0) {
  721.                              workMem = (MEMBLK *) ((byte *) cur + cur->size);
  722.                              workMem->prev = cur->prev;
  723.                         }
  724.  
  725.                         if (cur == mst[cur->segment].free)
  726.                                 mst[cur->segment].free = workMem;
  727.  
  728.                         if (cur == mst[cur->segment].last)
  729.                                 mst[cur->segment].last = workMem;
  730.  
  731.                 }
  732.         }
  733.  
  734.         /* If not combined, link into free chain */
  735.  
  736.         if (!combined) {
  737.  
  738.                 /* We scan backwards looking for the last block that
  739.                    is free */
  740.  
  741.                 workMem = cur->prev;
  742.  
  743.                 while ((workMem != NULL) && ((workMem->flags &
  744.                                                           BLK_INUSE) != 0)) {
  745.                         workMem = workMem->prev;
  746.                 }
  747.  
  748.                 /* A block is prior to the free block in memory */
  749.  
  750.                 if (workMem != NULL) {
  751.                         workFree = (FREEBLK *) DATALOC(workMem);
  752.                         curFree->prev = workMem;
  753.                         curFree->next = workFree->next;
  754.                         workFree->next = cur;
  755.  
  756.                         if (curFree->next != NULL) {
  757.                                 workFree = (FREEBLK *) DATALOC(curFree->next);
  758.                                 workFree->prev = cur;
  759.                         }
  760.                 } else {        /* Place at beginning of list */
  761.                         curFree->prev = NULL;
  762.                         curFree->next = mst[cur->segment].free;
  763.  
  764.                         if (mst[cur->segment].free != NULL) {
  765.                          workFree=(FREEBLK *) DATALOC(mst[cur->segment].free);
  766.                          workFree->prev = cur;
  767.                         }
  768.                         mst[cur->segment].free = cur;
  769.                 }
  770.         }
  771.  
  772.         if (mst[cur->segment].last == NULL) {
  773.                 mst[cur->segment].last = cur;
  774.                 mst[cur->segment].free = cur;
  775.         }
  776. }
  777.  
  778. /**     MemGetLargest   -- returns size of largest block available after
  779.                            compaction
  780.         Entry   none
  781.         Exit    none
  782.         Returns Free space in segment with most free space, less the size of
  783.                 one block header.
  784. **/
  785. uint
  786. MemGetLargest()
  787. {
  788.         byte    seg;                            /* Current segment */
  789.         uint    largest = 0;                    /* Free space */
  790.  
  791.         for (seg = 0; seg < numSegs; seg++)
  792.                 if (largest < mst[seg].freeSpace)
  793.                         largest = mst[seg].freeSpace;
  794.  
  795.         if (largest < sizeof(MEMBLK))
  796.                 return  0;
  797.         else
  798.                 return  largest - sizeof(MEMBLK);
  799. }
  800.  
  801. /**     MemGetCurrentLargest    -- returns size of largest available block
  802.         Entry   none
  803.         Exit    none
  804.         Returns size of largest available block
  805. **/
  806. uint
  807. MemGetCurrentLargest()
  808. {
  809.         byte    seg;                            /* Current segment */
  810.         MEMBLK  *curBlock;                      /* Current block */
  811.         FREEBLK *curFree;                       /* Current free block */
  812.         uint    largest = 0;                    /* Largest block found */
  813.  
  814.         for (seg = 0; seg < numSegs; seg++) {
  815.                 curBlock = mst[seg].free;
  816.                 while (curBlock != NULL) {
  817.                         if (curBlock->size > largest) {
  818.                                 largest = curBlock->size;
  819.                         }
  820.                         curFree = (FREEBLK *) DATALOC(curBlock);
  821.                         curBlock = curFree->next;
  822.                 }
  823.         }
  824.  
  825.         if (largest < sizeof(MEMBLK))
  826.                 return  0;
  827.         else
  828.                 return  largest - sizeof(MEMBLK);
  829. }
  830.  
  831. /**     MemCompact      -- invoke compaction routine
  832.         Entry   none
  833.         Exit    none
  834.         Returns none
  835. **/
  836. void
  837. MemCompact()
  838. {
  839.         byte    seg;
  840.  
  841.         for (seg = 0; seg < numSegs; seg++) {
  842.                 CompactSeg(seg, DEFSEGSIZE, FALSE);
  843.         }
  844. }
  845.  
  846. /**     CompactSeg      -- compact a segment
  847.         Entry   seg             segment to compact
  848.                 size            desired free block size
  849.                 deletable       TRUE if deletable segments should be deleted
  850.                                 FALSE otherwise
  851.         Exit    none
  852.         Returns none
  853. **/
  854. static void
  855. CompactSeg(seg, size, deletable)
  856. byte    seg;
  857. uint    size;
  858. int     deletable;
  859. {
  860.         MEMBLK  *copyLoc = NULL;                /* Next place to copy */
  861.         FREEBLK *copyFree;                      /* Free pointers */
  862.         MEMBLK  *curBlk;                        /* First block */
  863.         MEMBLK  *saveBlk;                       /* Saved block location */
  864.         MEMBLK  *prevBlk = NULL;                /* Previous block */
  865.         MEMBLK  *nextFree = NULL;               /* Saved next free block */
  866.         MEMBLK  *prevFree = NULL;               /* Saved prev. free block */
  867.         FREEBLK *tmpFree;                       /* Temporary free pointer */
  868.         uint    spaceRecovered = 0;             /* Amount space recovered */
  869.         int     last = FALSE;                   /* Last record found */
  870.  
  871.         curBlk = mst[seg].block;
  872.  
  873.         while ((spaceRecovered < size) && (!last)) {
  874.  
  875.                 last = (curBlk->flags & BLK_LAST) != 0;
  876.  
  877.                 if (((curBlk->flags & BLK_DELETABLE) != 0) && (deletable) &&
  878.                              (curBlk->size > sizeof(MEMBLK) + MINBLOCKDATA)) {
  879.                         spaceRecovered += curBlk->size - sizeof(MEMBLK) -
  880.                                                                  MINBLOCKDATA;
  881.  
  882.                         if (copyLoc != NULL) {
  883.  
  884.                                 if ((curBlk->flags & BLK_FUNCDELETE) != 0)
  885.                                      (*(curBlk->func))(curBlk, BLK_FUNCDELETE
  886.                                        | BLK_FUNCMOVE, curBlk->size, copyLoc);
  887.  
  888.                                 /* Save location of block */
  889.  
  890.                                 saveBlk = curBlk;
  891.  
  892.                                 /* Move block header to new location */
  893.                                 memmove(copyLoc, curBlk, sizeof(MEMBLK));
  894.  
  895.                                 /* Set up new pointer to previous block */
  896.  
  897.                                 copyLoc->prev = prevBlk;
  898.                                 copyLoc->flags &= ~BLK_LAST;
  899.                                 copyLoc->flags |= BLK_DELETED;
  900.                                 copyLoc->size = sizeof(MEMBLK) + MINBLOCKDATA;
  901.                                 mpt[copyLoc->pointerNum] = DATALOC(copyLoc);
  902.                                 prevBlk = copyLoc;
  903.                                 curBlk = (MEMBLK *) ((byte *) saveBlk +
  904.                                                                copyLoc->size);
  905.                                 copyLoc = (MEMBLK *) ((byte *) copyLoc +
  906.                                                                copyLoc->size);
  907.  
  908.                         } else {
  909.                                 if ((curBlk->flags & BLK_FUNCDELETE) != 0)
  910.                                         (*(curBlk->func))(curBlk,
  911.                                           BLK_FUNCDELETE, curBlk->size, NULL);
  912.  
  913.                                 /* Initialize free area after block */
  914.  
  915.                                 curBlk->flags &= ~BLK_LAST;
  916.                                 curBlk->flags |= BLK_DELETED;
  917.                                 saveBlk = curBlk;
  918.                                 prevBlk = curBlk;
  919.                                 curBlk = (MEMBLK *) ((byte *) curBlk +
  920.                                                                 curBlk->size);
  921.                                 saveBlk->size = sizeof(MEMBLK) + MINBLOCKDATA;
  922.                                 copyLoc = (MEMBLK *) DATALOC(saveBlk);
  923.  
  924.                         }
  925.  
  926.                 } else if ((curBlk->flags & BLK_INUSE) != 0) {
  927.                         if (copyLoc == NULL) {
  928.                                 prevBlk = curBlk;
  929.                                 curBlk  = (MEMBLK *) ((byte *) curBlk +
  930.                                                                 curBlk->size);
  931.                         } else {
  932.                                 if ((curBlk->flags & BLK_LOCKED) == 0) {
  933.                                       if ((curBlk->flags & BLK_FUNCMOVE) != 0)
  934.                                                 (*(curBlk->func))(curBlk,
  935.                                                    BLK_FUNCMOVE, curBlk->size,
  936.                                                        copyLoc);
  937.  
  938.                                         /* Move block to new location */
  939.  
  940.                                       saveBlk = curBlk;
  941.                                       memmove(copyLoc, curBlk, curBlk->size);
  942.  
  943.                                         copyLoc->prev           = prevBlk;
  944.                                         copyLoc->flags          &= ~BLK_LAST;
  945.                                         prevBlk                 = copyLoc;
  946.  
  947.                                         mpt[copyLoc->pointerNum] =
  948.                                                              DATALOC(copyLoc);
  949.  
  950.                                         /* Move pointer to next block */
  951.  
  952.                                       curBlk = (MEMBLK *) ((byte *)saveBlk +
  953.                                                                copyLoc->size);
  954.                                        copyLoc = (MEMBLK *) ((byte *)copyLoc +
  955.                                                                copyLoc->size);
  956.  
  957.                                 } else {   /* Close up current free block */
  958.  
  959.                                         curBlk = (MEMBLK *) ((byte *) curBlk +
  960.                                                                 curBlk->size);
  961.  
  962.                                         copyLoc->flags      = 0;
  963.                                         copyLoc->checkByte  = CB;
  964.                                         copyLoc->prev       = prevBlk;
  965.                                         copyLoc->size       = spaceRecovered;
  966.                                         copyLoc->pointerNum  = 0;
  967.                                         copyLoc->segment     = seg;
  968.                                         saveBlk =(MEMBLK *) ((byte *)copyLoc +
  969.                                                                copyLoc->size);
  970.                                         saveBlk->prev = copyLoc;
  971.                                         spaceRecovered  = 0;
  972.  
  973.                                         copyFree =(FREEBLK *)DATALOC(copyLoc);
  974.                                         copyFree->prev  = prevFree;
  975.                                         if (prevFree != NULL) {
  976.                                                 tmpFree = (FREEBLK *)
  977.                                                             DATALOC(prevFree);
  978.                                                 tmpFree->next = copyLoc;
  979.                                         }
  980.  
  981.                                         copyFree->next = nextFree;
  982.                                         if (nextFree != NULL) {
  983.                                                 tmpFree = (FREEBLK *)
  984.                                                             DATALOC(nextFree);
  985.                                                 tmpFree->prev = copyLoc;
  986.                                         }
  987.  
  988.                                         prevBlk         = copyLoc;
  989.                                         prevFree        = copyLoc;
  990.                                         copyLoc         = NULL;
  991.                                 }
  992.                         }
  993.                 } else {                /* Free */
  994.                         if (copyLoc == NULL)
  995.                                 copyLoc = curBlk;
  996.  
  997.                         spaceRecovered += curBlk->size;
  998.  
  999.                         nextFree = (MEMBLK *) (((FREEBLK *)
  1000.                                                       DATALOC(curBlk))->next);
  1001.                         curBlk = (MEMBLK *) ((byte *) curBlk + curBlk->size);
  1002.                 }
  1003.         }
  1004.  
  1005.         /* At this point copyLoc points to the beginning of the free area,
  1006.            spaceRecovered is the size of the new free block, and saveBlk
  1007.            points to the next free block in the segment */
  1008.  
  1009.         if (copyLoc != NULL) {
  1010.                 copyLoc->checkByte      = CB;
  1011.                 copyLoc->prev           = prevBlk;
  1012.                 copyLoc->size           = spaceRecovered;
  1013.                 copyLoc->pointerNum     = 0;
  1014.                 copyLoc->segment        = seg;
  1015.  
  1016.                 if (last) {
  1017.                         copyLoc->flags = BLK_LAST;
  1018.                 } else {
  1019.                        copyLoc->flags = 0;
  1020.                        saveBlk = (MEMBLK *)((byte *) copyLoc + copyLoc->size);
  1021.                        saveBlk->prev = copyLoc;
  1022.                 }
  1023.  
  1024.                 copyFree = (FREEBLK *) DATALOC(copyLoc);
  1025.                 copyFree->prev = prevFree;
  1026.                 if (prevFree != NULL) {
  1027.                         tmpFree = (FREEBLK *) DATALOC(prevFree);
  1028.                         tmpFree->next = copyLoc;
  1029.                 }
  1030.                 copyFree->next = nextFree;
  1031.                 if (nextFree != NULL) {
  1032.                         tmpFree = (FREEBLK *) DATALOC(nextFree);
  1033.                         tmpFree->prev = copyLoc;
  1034.                 }
  1035.                 mst[seg].free = copyLoc;
  1036.                 mst[seg].last = copyLoc;
  1037.         }
  1038. }
  1039.  
  1040.  
  1041. [LISTING THREE]
  1042.  
  1043. /*****  demo.c          Demonstration program for memory manager
  1044.         S. Peterson     programmer      1/89
  1045.         This program demonstrates the features of the memory manager.
  1046. **/
  1047. #include        <stdio.h>
  1048. #include        <stddef.h>
  1049. #include        <process.h>
  1050. #include        <memory.h>
  1051. #include        "mem.h"
  1052.  
  1053. void    blockFunc(void *, byte, uint, void *); /* Prototype, block function */
  1054. int     main(void);
  1055.  
  1056. int
  1057. main()
  1058. {
  1059.      void       **p;                            /* Double pointer to block */
  1060.      void       *q;                             /* Single pointer to block */
  1061.  
  1062.     /* Allocate a 30K buffer and 100 master pointers */
  1063.  
  1064.     if (MemInit(30000l, 100) != TRUE)
  1065.                 exit(1);
  1066.  
  1067.     /* Allocate a buffer of 1024 bytes.  It is created as moveable and
  1068.                 undeletable */
  1069.  
  1070.     if ((p = MemAlloc(1024)) == NULL)
  1071.                 printf("Error allocating 1024 bytes.\n");
  1072.  
  1073.      MemLock(p);                        /* Make the block unmoveable */
  1074.      q = *p;                            /* Get pointer to memory block */
  1075.      memset(q, 0, 1024);                /* Initialize block to 0 */
  1076.  
  1077.      MemUnlock(p);                      /* Make the block moveable */
  1078.                                         /* Note: q no longer valid */
  1079.  
  1080.      MemCompact();                      /* Cause memory to be compacted */
  1081.  
  1082.      MemFree(p);                        /* Deallocate p */
  1083.  
  1084.      /* Allocate a block with an associated function. */
  1085.  
  1086.      if ((p = MemAllocFunc(1024, blockFunc, BLK_FUNCDELETE |
  1087.                                                        BLK_FUNCMOVE)) == NULL)
  1088.                 exit(2);
  1089.  
  1090.      MemFree(p);                        /* Deallocate p */
  1091.  
  1092.      return     0;
  1093. }
  1094.  
  1095. void
  1096. blockFunc(blockPtr, flags, length, newLoc)
  1097. void    *blockPtr;
  1098. byte    flags;
  1099. uint    length;
  1100. void    *newLoc;
  1101. {
  1102.         if ((flags & BLK_FUNCMOVE) != 0) {
  1103.                 /* Perform some action when block moves */
  1104.         }
  1105.  
  1106.         if ((flags & BLK_FUNCDELETE) != 0) {
  1107.                 /* Perform some action when block is deleted */
  1108.         }
  1109. }
  1110.